TNotes.leetcode

Appearance

0137. 只出现一次的数字 II【中等】

0137. 只出现一次的数字 II【中等】 ​

1. 📝 题目描述 ​

给你一个整数数组 nums，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

txt
输入：nums = [2,2,3,2]
输出：3

示例 2：

txt
输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

  • 1 <= nums.length <= 3 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

2. 🫧 评价 ​

  • s.1 是解决“其他数出现 k 次，找唯一出现一次的数”这类问题的经典位运算技巧，是一个通用的解决方案。
  • s.2 走的也是位运算的逻辑，统计每一个数字的每一位的出现次数，非 3 的倍数则说明该位是有效位。
  • s.3 简单直观，但是不符合题目要求。
  • 提交结果对比：
s.1
s.2
s.3

3. 🎯 s.1 - 位运算 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let ones = 0,
    twos = 0

  for (const num of nums) {
    // ones 记录二进制位出现 1 次的数字，twos 记录出现 2 次的数字
    ones = (ones ^ num) & ~twos
    twos = (twos ^ num) & ~ones
  }

  return ones
}
  • 时间复杂度：O(n) - 遍历数组一次
  • 空间复杂度：O(1) - 只使用了两个变量
  • 解题思路
    • 对于每个二进制位，我们只关心它出现了 0 次、1 次、2 次（因为出现 3 次就相当于 0 次，模 3 后归零）。
    • 用两个整数 ones 和 twos 来共同表示每个位的状态：
      • ones 的某一位为 1：表示该位 模 3 余 1（即出现了 1 次）
      • twos 的某一位为 1：表示该位 模 3 余 2（即出现了 2 次）
      • 如果某一位在 ones 和 twos 中都是 0：表示该位出现了 0 次或 3 次（即模 3 为 0）
    • 因为题目保证 只有一个数字出现一次，其余都出现三次，所以最终只有那个“出现一次”的数字会留在 ones 中。
  • 状态转移
    • 对于每一位，随着新数字 num 的加入，状态按如下方式转移：
当前状态 (twos, ones)输入 bit新状态 (twos, ones)
(0, 0)0(0, 0)
(0, 0)1(0, 1)
(0, 1)1(1, 0)
(1, 0)1(0, 0)

这正好是 模 3 计数器 的行为。

  • 代码解释：
    • 初始化两个状态变量，所有位都是 0 let ones = 0, twos = 0
    • 第一步：更新 ones -> ones = (ones ^ num) & ~twos
      • ones ^ num：尝试把 num 加入“出现一次”的状态。
      • 但要 排除那些已经在 twos 中为 1 的位（即已经出现两次的位），因为如果某位已经在 twos 中，说明再加一次就变成三次，应该归零，不能进入 ones。
      • 所以用 & ~twos 屏蔽掉 twos 为 1 的位。
    • 第二步：更新 twos -> twos = (twos ^ num) & ~ones
      • twos ^ num：尝试把 num 加入“出现两次”的状态。
      • 但要 排除那些在新的 ones 中为 1 的位，因为如果某位刚被加入 ones（即现在只出现一次），就不能同时在 twos 中。
      • 注意：这里用的是 刚更新后的 ones，所以顺序不能颠倒！
    • 注意：顺序很重要：必须先更新 ones，再用新的 ones 更新 twos。
  • 巧妙利用两个变量模拟 三进制计数器，通过位运算实现模 3 计数。
  • 这是解决“其他数出现 k 次，找唯一出现一次的数”这类问题的经典位运算技巧，类似地可以得出：
    • 如果其他数出现 两次，只需 xor 所有数即可；
    • 如果出现 四次，则需要三个状态变量，或者也按照 两次 的处理逻辑来写，借助异或运算两两抵消的特性；
    • …… 以此类推

4. 🎯 s.2 - 统计每一位出现的次数 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  let result = 0

  // 对于32位整数的每一位
  for (let i = 0; i < 32; i++) {
    let count = 0

    // 统计第 i 位上为 1 的数字个数
    for (const num of nums) {
      if ((num >> i) & 1) {
        count++
      }
    }

    // 如果不能被 3 整除，说明只出现一次的数字在第 i 位上是 1
    if (count % 3 !== 0) {
      result |= 1 << i
    }
  }

  return result
}
  • 时间复杂度：O(n) - 外层循环 32 次，内层循环 n 次，总体仍是线性时间
  • 空间复杂度：O(1) - 只使用常数额外空间

5. 🎯 s.3 - 使用 Map 计数 ​

js
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function (nums) {
  const map = new Map()

  // 统计每个数字出现的次数
  for (const num of nums) {
    map.set(num, (map.get(num) || 0) + 1)
  }

  // 找到出现次数为 1 的数字
  for (const [num, count] of map) {
    if (count === 1) {
      return num
    }
  }
}
  • 时间复杂度：O(n) - 遍历数组两次
  • 空间复杂度：O(n) - 使用 Map 存储所有不同的数字
    • 不符合 常数级空间 的要求

Discussions